package com.peng.tree.test_code.dp;

import com.peng.tree.Node;

/**
 * 给定一棵二叉树的头节点head，和另外两个节点a和b。
 * 返回a和b的最低公共祖先
 * 以X展开讨论：
 * 1、与X有关：
 * 1.1：A,B分别位于左右两树 ，最低公共祖先为X
 * 1.2：A或B本身为a(b)节点，左树或者右树找到b(a)节点
 * 2、与X无关，A,B的最早公共祖先出现在左树或者右树上
 */
public class Test13_GetLowestAncestor {

    public static Node getLowestAncestor(Node head, Node a, Node b) {
        if (head == null) {
            return null;
        }
        return process(head, a, b).lowestAncestor;
    }

    public static TreeInfo process(Node head, Node a, Node b) {
        if (head == null) {
            return new TreeInfo(null, false, false);
        }
        TreeInfo leftInfo = process(head.left, a, b);
        TreeInfo rightInfo = process(head.right, a, b);
        boolean findA = (head == a) || leftInfo.findA || rightInfo.findA;
        boolean findB = (head == b) || leftInfo.findB || rightInfo.findB;
        Node lowerAncestor = null;
        if (leftInfo.lowestAncestor != null) {
            lowerAncestor = leftInfo.lowestAncestor;
        } else if (rightInfo.lowestAncestor != null) {
            lowerAncestor = rightInfo.lowestAncestor;
        } else {
            if (findA && findB) {
                lowerAncestor = head;
            }
        }


        return new TreeInfo(lowerAncestor, findA, findB);
    }

    public static void main(String[] args) {
        Node node = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);

        node.left = node2;
        node.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        //        node4.left = node8;
//        node4.right = node9;
        /*
                   1
             2              3
           4    5         6     7
         8   9

         */

        System.out.println(getLowestAncestor(node, node4, node4).value);
    }

    static class TreeInfo {
        Node lowestAncestor;
        boolean findA;
        boolean findB;

        public TreeInfo(Node lowestAncestor, boolean findA, boolean findB) {
            this.lowestAncestor = lowestAncestor;
            this.findA = findA;
            this.findB = findB;
        }
    }


}
